/*
 * Copyright (c) 2019 Wormpex.com. All Rights Reserved.
 */

package com.sk.leetcode.arithmetic;

import com.alibaba.fastjson.JSON;

import java.util.List;

/**
 * 直线上最多的点数
 * 给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
 * <p>
 * 输入: [[1,1],[2,2],[3,3]]
 * 输出: 3
 * 解释:
 * ^
 * |
 * |        o
 * |     o
 * |  o
 * +------------->
 * 0  1  2  3
 * <p>
 * <p>
 * 示例 2:
 * <p>
 * 输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
 * 输出: 4
 * 解释:
 * ^
 * |
 * |  o
 * |     o        o
 * |        o
 * |  o        o
 * +------------------->
 * 0  1  2  3  4  5  6
 * <p>
 * <p>
 * 链接：https://leetcode-cn.com/problems/max-points-on-a-line
 *
 * @author ke.su date: 2019-09-06 Time: 上午11:00
 * <p>
 * <p>
 * <p>
 *     有屎以来最好成绩
 * 执行用时 :18 m , 在所有 Java 提交中击败了 90.19% 的用户
 * 内存消耗 :35.3 MB , 在所有 Java 提交中击败了82.18%的用户
 *
 *
 * 算法及注意点：
 * 1，采用三重循环的最笨方法
 * 2，相同的点要单独计算-
 * 3，相同的点，每个起始点相同时，只计算一次
 *
 */
public class Test149 {

    public static void main(String[] args) {
        int[][] points = new int[][]{{1, 1}, {1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}, {1, 1}, {1, 1}, {1, 1}, {1, 1}, {1, 1}};
        int[][] points0 = new int[][]{{1, 1}, {1, 1}, {2, 3}, {3, 4}, {4, 5}, {6, 7}, {7, 8}, {8, 9}, {1, 1}, {1, 1}, {1, 1}, {1, 1}};
        int[][] points1 = new int[][]{{1, 1}, {1, 1}, {2, 2}, {5, 5}, {4, 4}, {2, 3}, {1, 4}, {1, 1}, {1, 1}, {1, 1}, {1, 1}, {1, 1}};
        int[][] points2 = new int[][]{{1, 1}, {1, 1}, {1, 1}};
        int[][] points3 = new int[][]{{0, 0}, {1, 65536}, {65536, 0}};
        int[][] points5 = new int[][]{{-1, 0}, {-1, 3}, {65536, 0}};

        String s = "[[2,76],[4,77],[-3,80],[2,3],[-3,80],[-3,80],[-3,80],[-3,80],[2,4],[3,5],[2,75]]";

        String point5 = "[[40,-23],[9,138],[429,115],[50,-17],[-3,80],[-10,33],[5,-21],[-3,80],[-6,-65],[-18,26],[-6,-65],[5,72],[0,77],[-9,86],[10,-2],[-8,85],[21,130],[18,-6],[-18,26],[-1,-15],[10,-2],[8,69],[-4,63],[0,3],[-4,40],[-7,84],[-8,7],[30,154],[16,-5],[6,90],[18,-6],[5,77],[-4,77],[7,-13],[-1,-45],[16,-5],[-9,86],[-16,11],[-7,84],[1,76],[3,77],[10,67],[1,-37],[-10,-81],[4,-11],[-20,13],[-10,77],[6,-17],[-27,2],[-10,-81],[10,-1],[-9,1],[-8,43],[2,2],[2,-21],[3,82],[8,-1],[10,-1],[-9,1],[-12,42],[16,-5],[-5,-61],[20,-7],[9,-35],[10,6],[12,106],[5,-21],[-5,82],[6,71],[-15,34],[-10,87],[-14,-12],[12,106],[-5,82],[-46,-45],[-4,63],[16,-5],[4,1],[-3,-53],[0,-17],[9,98],[-18,26],[-9,86],[2,77],[-2,-49],[1,76],[-3,-38],[-8,7],[-17,-37],[5,72],[10,-37],[-4,-57],[-3,-53],[3,74],[-3,-11],[-8,7],[1,88],[-12,42],[1,-37],[2,77],[-6,77],[5,72],[-4,-57],[-18,-33],[-12,42],[-9,86],[2,77],[-8,77],[-3,77],[9,-42],[16,41],[-29,-37],[0,-41],[-21,18],[-27,-34],[0,77],[3,74],[-7,-69],[-21,18],[27,146],[-20,13],[21,130],[-6,-65],[14,-4],[0,3],[9,-5],[6,-29],[-2,73],[-1,-15],[1,76],[-4,77],[6,-29]]";

        //System.out.println(maxPoints1(points));
        // System.out.println(maxPoints1(points0));
        // System.out.println(maxPoints1(points1));
        // System.out.println(maxPoints1(points2));
        //System.out.println(maxPoints1(points3));
        //System.out.println(maxPoints1(points6));
        System.out.println(maxPoints1(getPoint(point5)));
        System.out.println(maxPoints1(getPoint(s)));


    }

    private static int[][] getPoint(String p) {
        List<int[]> l = JSON.parseArray(p, int[].class);
        //System.out.println(JSON.toJSONString(l));
        int[][] point = new int[l.size()][2];
        for (int i = 0; i < l.size(); i++) {
            point[i] = l.get(i);
        }
        return point;
    }


    public static int maxPoints1(int[][] points) {
        if (points.length < 3) {
            return points.length;
        }
        //最笨的方法，全部轮一遍
        int ret = 2;
        for (int i = 0; i < points.length; i++) {
            int maxLength = 1, someNum = 0;
            boolean b = true;
            for (int j = i + 1; j < points.length; j++) {

                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];

                if (x == 0 && y == 0 && b) {
                    someNum++;
                    continue;
                }

                maxLength++;
                for (int k = j + 1; k < points.length; k++) {
                    long x0 = points[k][0] - points[i][0];
                    long y0 = points[k][1] - points[i][1];

                    if (x * y0 == y * x0) {
                        maxLength++;
                    }
                }
                ret = Math.max(maxLength + someNum, ret);
                maxLength = 1;
            }
            ret = Math.max(maxLength + someNum, ret);
            b = false;
        }

        return ret;
    }
}
